(* Run-length encoding of a list *)

(* 函数功能：
将连续重复的元素压缩为(计数,元素)的元组形式
例如输入 [a; a; a; b; b; c] 会输出 [(3,a); (2,b); (1,c)]
实现特点：
使用尾递归辅助函数aux进行核心处理
通过模式匹配处理三种情况：空列表、单元素列表和多元素列表
使用累加器acc收集结果，最后用List.rev反转保持原始顺序
当遇到不同元素时重置计数器(count=0)
关键逻辑：
递归遍历列表，比较相邻元素
相同则计数器+1继续递归
不同则将当前计数结果存入累加器并重置计数器
处理最后一个元素时自动终止
边界处理：
空列表直接返回空
单元素列表会正确编码为(1,元素)
保持元素原始顺序（通过List.rev实现） *)

let encode list = 
  let rec aux count acc = function
    | [] -> [] (* Can only be reached if original list is empty *)
    | [x] -> (count + 1, x) :: acc
    | a :: (b :: _ as t) -> if a = b then aux (count + 1) acc t else aux 0 ((count + 1, a) :: acc) t
  in
  List.rev (aux 0 [] list) 
;;

assert (encode [`a;`a;`a;`a;`b;`c;`c;`a;`a;`d;`e;`e;`e;`e] = 
    [4,`a ; 1,`b ; 2,`c ; 2,`a ; 1,`d ; 4,`e]) ;;

